In advanced semiconductor manufacturing technology nodes, multiple-patterning lithography has been widely used to push the lithography limitation. Multiple patterning (or multi-patterning) is a class of technologies for manufacturing integrated circuits (ICs), developed for photolithography to enhance the feature density. Design patterns in a layout are decomposed into multiple groups, where in each group, the spacing between all patterns should be larger than a given minimum spacing. The layout decomposition problem is usually formulated as a coloring problem, and design patterns assigned with different colors are separated formed on different manufacturing masks. Design methodologies for multiple patterning can be categorized into (1) colorless techniques and (2) pre-coloring techniques.